package leetcode.editor.cn;

import java.util.Arrays;

/**
 * @author Administrator
 * @description 前序遍历构造二叉搜索树 1008
 * @date 2023/3/11 0011
 */
public class Solution1008 {

    public static void main(String[] args) {
        int[] test = {4,2};
        Solution1008 t = new Solution1008();
        TreeNode treeNode = t.bstFromPreorder(test);
    }

    public TreeNode bstFromPreorder(int[] preorder) {
        int len = preorder.length;
        int[] inorder = Arrays.copyOf(preorder, len);
        Arrays.sort(inorder);
        return buildTree(preorder, 0, len-1, inorder, 0, len-1);

    }

    private TreeNode buildTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
        if (preStart > preEnd || inStart > inEnd) {
            return null;
        }
        int rootVal = preorder[preStart];
        int index = -1;
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == rootVal) {
                index = i;
                break;
            }
        }

        TreeNode root = new TreeNode(rootVal);
        if (index == -1) {
            return root;
        }

        int leftSize = index - inStart;

        root.left = buildTree(preorder, preStart + 1, preStart + leftSize,
                inorder, inStart, index - 1);
        root.right = buildTree(preorder, preStart + leftSize +1, preEnd,
                inorder, index + 1, inEnd);
        return root;
    }

}
